package com.hdu.other.dp.pakege01;

public class lc494 {
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            /**
             * x + y = sum
             * x - y = target
             *
             * x = (sum + target) / 2
             */

            boolean p1 = (sum + target) % 2 == 1;
            boolean p2 = target > 0 && target > sum;
            boolean p3 = target < 0 && -target > sum;

            if (p1 || p2 || p3) {
                return 0;
            }

            int size = (sum + target) / 2;
            int[] dp = new int[size + 1];
            dp[0] = 1;
            for (int i = 0; i < nums.length; i++) {
                for (int j = size; j >= nums[i]; j--) {
                    dp[j] += dp[j - nums[i]];
                }
            }
            return dp[size];
        }
    }
}
